
from typing import List


class Solution:
    """回溯"""

    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def generate_board(row: List[List[int]]):
            board = []
            for i in row:
                tmp = "." * i + "Q" + "." * (n - i - 1)
                board.append(tmp)
            return board
        def queen(A, cur=0):
            if cur == len(A):
                res.append(generate_board(A))
                return 0
            for col in range(len(A)):
                A[cur], flag = col, True
                for row in range(cur):
                    if A[row] == col or abs(col - A[row]) == cur - row:
                        flag = False
                        break
                if flag:
                    queen(A, cur+1)
        queen([None]* n)
        return res

res = Solution().solveNQueens(4)
print(res)
